package Leetcode;

/**
 * https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 *
 * 一个排序数组，找到目标元素开始和结束的地方

 * Input: nums = [5,7,7,8,8,10], target = 8
 * Output: [3,4]
 *
 *记住是左闭区间、有闭区间， 注意这个区间~~
 *
 * 二分查找 https://mp.weixin.qq.com/s/uA2suoVykENmCQcKFMOSuQ
 *
 */
public class L704_BinarySearch {
    public int search(int[] nums, int target) {
        int left=0,mid;
        int right=nums.length-1;//注意，这里是取最后一个元素的下标
        while (left <= right){ //有等号是因为这是闭区间，如果正好相等还要判断下
            //这里为了避免溢出，还可以 int mid = left + (right-left)/2; 先减 再加 就不会溢出了
            mid = (left + right) / 2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){ //目标在左边，缩小右边的区间
                right = mid - 1;//当前mid已经对比过了，不是，所以，mid-1
            }else if(nums[mid] < target){//目标在右边，缩小左边的区间
                left = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 要取最左边的，那就要 这个搜索区间是 [left, right) 左闭右开
     */
    public int left_bound(int[] nums, int target){
        if(nums.length == 0) return -1;
        int left = 0,mid;
        int right = nums.length;

        while (left < right){ //因为右边是开区间了，不能相等
            mid = (left + right)/2;
            if(nums[mid] == target){//这里要注意，不是直接返回，是当成>的情况
                right = mid;
            }else if(nums[mid] > target){//目标在左边
                right = mid;//开区间，所以，这里
            }else if(nums[mid] < target){//当前数比目标小，说明在右边，左边要缩小
                left = mid + 1;//闭区间，所以，这里left加上去
            }
        }
        //最后下来，如果找到了，那left就对了，如果没找到，直接判断是否相等就可以了
        if(left == nums.length) return -1;//target比所有数都要大
        return nums[left] == target ? left : -1;
    }

    /**
     * 要取最右边的，那就要 这个搜索区间是 (left, right] 左开右闭
     */
    public int right_bound(int[] nums, int target){
        if(nums.length == 0) return -1;
        int left = 0,mid;
        int right = nums.length; //这里是跟left一样的！！！！ 不要自作聪明

        while (left < right){ //因为右边是开区间了，不能相等
            mid = (left + right)/2;
            if(nums[mid] == target){//这里要注意，不是直接返回，是当成>的情况，这里左边的往右移
                left = mid + 1;//当 nums[mid] == target 时，不要立即返回，而是增大「搜索区间」的下界 left，使得区间不断向右收缩，达到锁定右侧边界的目的。
            }else if(nums[mid] > target){//目标在左边
                right = mid;//开区间，所以，这里
            }else if(nums[mid] < target){//当前数比目标小，说明在右边，左边要缩小
                left = mid + 1;//闭区间，所以，这里left加上去
            }
        }
        //因为我们对 left 的更新必须是 left = mid + 1，就是说 while 循环结束时，nums[left] 一定不等于 target 了，而 nums[left-1] 可能是 target。
        if(left == 0) return -1;//因为mid+1了，所以，有相等的不会是0，就是找不到
        return left - 1;
    }

    //用 1 1 来做例子，最好理解
    public static void main(String[] args){
        L704_BinarySearch a = new L704_BinarySearch();
        int[] aa = new int[]{1,1};
        a.right_bound(aa, 1);
    }

}
